package com.leetcode.algorithms.one.problem3;

import java.util.HashMap;
import java.util.Map;

public class LongestDistinctSubString {
	public static int longestSub(String s) {
		if (s == null || "".equals(s))
			return 0;

		char[] cs = s.toCharArray();
		Map<Character, Integer> map = new HashMap<>();
		map.put(cs[0], 0);

		// i代表当前下标
		int i = 1, len = 1, max = 1, j = 1;
		for (; i < cs.length; i++) {
			if (map.containsKey(cs[i])) {

				j = map.get(cs[i]);
				max = max > len ? max : len;
				map.clear();
				map.put(cs[j + 1], j + 1);
				len = 1;
				i = j + 1;
			} else {
				len++;
				map.put(cs[i], i);
			}
		}
		return max > len ? max : len;
	}

	public static int superSolution(String s){
		if(s==null||"".equals(s))
			return 0;
		
		int head=0,point=1,max=1,tmp=0;
		char[] cs = s.toCharArray();
		for(;point<cs.length;point++){
			
			
			
			tmp = s.indexOf(cs[point], head);
			if(tmp!=point){
				max =Math.max(max, point-head);
				head = tmp+1;
				if(cs.length-head<=max)
					return max;
			}
		}
		
		
		return point-head;
	}
	
	
	public static int slidingWindow(String s) {

		char[] cs = s.toCharArray();
		int max = 0;
		Map<Character, Integer> map = new HashMap<>(); // current index of
														// character
		for (int i = 0, j = -1; i < cs.length; i++) {
			if (map.containsKey(cs[i])) {
				j =Math.max(map.get(cs[i]),j);
//				j =map.get(cs[i]);
			}
			max = Math.max(max, i-j);
			if(cs.length-j<=max)
				return max;
			map.put(cs[i], i);
		}
		return max;
	}

	public static int slidingWindow1(String s) {
		if("".equals(s))
			return 0;

		char[] cs = s.toCharArray();
		int pointer=0,head=0,max = 0;
		Map<Character, Integer> map = new HashMap<>(); // current index of
														// character
		for (; pointer < cs.length; pointer++) {
			if (map.containsKey(cs[pointer])) {
				
				max = Math.max(max, pointer-head);
//				head=map.get(cs[pointer])+1;
				head =Math.max(map.get(cs[pointer])+1,head);
//				max = Math.max(max, pointer-head);
				if(cs.length-head<=max)
					return max;
			}
			map.put(cs[pointer], pointer);
		}
		return pointer-head;
	}
	
	public static void main(String[] args) {

		String s="tmmzuxt";
		System.out.println(slidingWindow1(s));

		
	}
}
